package com.lw.leetcode.tree.b;

import com.lw.leetcode.linked.ListNode;
import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 面试题 04.03. 特定深度节点链表
 *
 * @Author liw
 * @Date 2021/5/21 22:12
 * @Version 1.0
 */
public class ListOfDepth {

    public ListNode[] listOfDepth(TreeNode tree) {
        List<ListNode> list = new ArrayList<>();
        Queue<TreeNode> a = new ArrayDeque<>();
        Queue<TreeNode> b = new ArrayDeque<>();
        a.add(tree);
        while (!a.isEmpty()) {
            ListNode f = new ListNode(0);
            ListNode item = f;
            while (!a.isEmpty()) {
                TreeNode poll = a.poll();
                if (poll.left != null) {
                    b.add(poll.left);
                }
                if (poll.right != null) {
                    b.add(poll.right);
                }
                ListNode node = new ListNode(poll.val);
                item.next = node;
                item = node;
            }
            list.add(f.next);
            if (b.isEmpty()) {
                break;
            }
            a = b;
            b = new ArrayDeque<>();
        }
        ListNode[] arr = new ListNode[list.size()];
        for (int i = 0, size = list.size(); i < size; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }


}
